In a computer system, virtual memory management automates the movement of instructions and data between physical memory and secondary storage (e.g., disk storage, etc.) giving the appearance of a single, large memory unit. Conceptually, the address space of a processor is divided into virtual memory pages of a uniform size and the physical memory is divided into physical memory pages of the same size. While applications are executing, the operating system (OS) and the memory management unit (MMU) of the processor work together to move virtual memory pages into and out of the physical memory pages as needed. The OS and MMU use virtual-to-physical address mapping information to translate virtual memory addresses from the processor into physical memory addresses behind the scenes, creating the illusion of a single-level store with access time of random-access memory rather than that of secondary storage.
In many virtual memory implementations, virtual-to-physical address mapping information is stored in memory management data structures managed by the OS and is cached in a translation lookaside buffer (TLB) in the MMU. This virtual-to-physical address mapping information generally includes a virtual page number. If the virtual memory page is in physical memory, the virtual-to-physical address mapping information also contains the physical page number of the physical memory page containing the virtual memory page. Other information may also be included such as whether the page holds executable code and whether the page can be modified, and, if so, by whom. In complex virtual memory management systems supporting multiple address space contexts, the mapping information may also include an address space context identifier.
The virtual-to-physical address mapping information may be stored in different formats, depending on the virtual memory implementation. In some implementations, the memory management data structures are referred to as page tables and the virtual-to-physical address mapping information is stored as a page table entry (PTE). The PTEs are stored in the format expected by the TLB and are moved without translation from the page table to the TLB by the OS and/or hardware page table handlers. In more complex virtual memory management implementations, more complex data structures may exist that represent the state of the virtual memory. For example, in some systems, the OS creates translation table entries (TTEs) (i.e., entries that include the virtual-to-physical address mapping information) by extracting the mapping information from the more complex software representation. These TTEs are stored in an intermediate software cache known as a translation software buffer (TSB). The TTEs are stored in the format expected by the TLB. The OS uses the TSB to load entries in the TLB. A TTE and a PTE are functionally equivalent; each holds virtual-to-physical address mapping information for a single virtual memory page. Hereinafter, any reference to a mapping entry applies equally to a PTE or a TTE.
The TLB is a cache of mapping entries for recently used virtual memory pages. The TLB takes as input a virtual page identifier including at least a virtual page number and returns the corresponding physical page number if the mapping entry identified by the virtual page identifier is in the TLB. When the processor requests a fetch or store operation from virtual memory, the virtual address is passed to the MMU. The virtual page identifier from the virtual address is provided to the TLB. If the corresponding mapping entry is in the TLB, the corresponding physical page number is returned and the MMU creates a physical memory address using the physical page number and indexing information from the virtual address and puts the physical address on an address bus. If the mapping entry is not in the TLB, a TLB miss occurs.
The TLB miss is handled by moving a mapping entry corresponding to the virtual address into the TLB, which may be done in hardware, by the OS, or by some combination of the two. In general, if the requested virtual memory page is in physical memory, the corresponding mapping entry is placed in the TLB and the address translation is completed. A page fault occurs if a requested virtual memory page is not mapped into physical memory such as when the virtual memory page has never been accessed, has never been created, or has been swapped out to secondary storage to make room in physical memory for another virtual memory page.
If a page fault occurs and the desired virtual memory page is in secondary storage, the OS copies the virtual memory page into a physical memory page and updates the mapping entry accordingly. If the virtual memory page has not been created, the OS creates a new virtual memory page and places it in a physical memory page, updating the mapping entry accordingly. If a physical memory page is not available, the OS makes room for the requested virtual memory page by demapping and swapping out another virtual memory page. If a virtual memory page is demapped, the OS ensures that any references to the demapped page are removed from the TLB and from any cache. After the page fault is handled, the updated mapping entry for the loaded page is placed in the TLB and the address translation is completed.
In a multiprocessor, shared-memory computer system, each processor has an MMU and TLB while sharing physical memory with the other processors. At any given time during execution, the same mapping entry may be in the TLBs of multiple of the processors. Data or instructions from the virtual memory page may also be represented by the mapping entry in multiple of the processors' caches. If a mapping entry is in a TLB, the associated page is assumed to be in physical memory. Therefore, if the OS demaps a virtual memory page, the OS ensures that all processors are aware of the change. That is, the OS ensures that the TLBs and any affected caches are coherent. In some implementations, the OS maintains this coherency by making a cross call to all processors. The act of performing a cross call forces each processor to flush the mapping entry representing the demapped virtual memory page from the processor's TLB and to flush affected entries from the processor's caches. Cross calls are essentially CPU-to-CPU interrupts, typically used for MMU related coherency tasks. The cross call operation may force a potentially unnecessary synchronization, i.e., the page mapping affected may never be used again by one or more of the processors or one or more of the processors may not have the mapping.